/*
 * revert_link_list.cpp
 * Copyright (C) 2016 libo <libo@tencent.com>
 *
 * Distributed under terms of the MIT license.
 */

#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node {
  int value;
  Node* next;
  Node() {
    value = 0;
    next = NULL;
  };
  Node(int v) {
    value = v;
    next = NULL;
  };
};

Node* reverse_link_list(Node* head) {
  if (head->next == NULL) return head;
  Node* cur_ptr = head;
  Node* next_ptr = head->next;
  cur_ptr->next = NULL;
  while (next_ptr != NULL) {
    Node* tmp_ptr = next_ptr->next;
    next_ptr->next = cur_ptr;
    cur_ptr = next_ptr;
    next_ptr = tmp_ptr;
  }
  return cur_ptr;
}

void print_link_list(Node* head) {
  Node* cur_ptr = head;
  while (true) {
    cout << cur_ptr->value << " ";
    if (cur_ptr->next == NULL) break;
    cur_ptr = cur_ptr->next;
  }
}


int main() {
  int list[] = {1,2,3,4,5};
  Node *head = NULL, *last = NULL;
  for (int i = 0; i < 5; ++i) {
    Node* one_node = new Node(list[i]);
    if (head == NULL) head = one_node;
    if (last != NULL) last->next = one_node;
    last = one_node;
  } 
  print_link_list(head);
  cout << "\n";
  Node* new_head = reverse_link_list(head);
  if (new_head != NULL)
    print_link_list(new_head);
  cout << "\n";
  return 0;
}
